// https://leetcode.cn/problems/word-break/

// 题干：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。
//      如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
//      注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

// 示例：输入: s = "leetcode", wordDict = ["leet", "code"]
//      输出: true

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        // dp[i]表示[0,i]区间内的字符串，能否被字典中的单词拼接而成
        int n = s.size();
        s = " " + s;
        vector<bool> dp(n + 1, false); dp[0] = true;

        unordered_set<string> hash;
        for (const auto& str : wordDict) hash.insert(str);

        for (int i = 1 ; i <= n ; i++){
            for (int j = 1 ; j <= i ; j++){
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1))){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

int main()
{
    Solution sol;
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};

    cout << sol.wordBreak(s, wordDict) << endl;

    return 0;
}









